impl Solution {
    pub fn get_money_amount(n: i32) -> i32 {
        let mut bp=vec!(vec!(-1;(n+1) as usize);(n+1) as usize);
        for i in 0..(n+1) as usize{
            bp[i][i]=0;
        };
        Solution::get_f(1,n as usize,&mut bp)
    }
    fn get_f(i :usize, j :usize,bp :&mut[Vec<i32>])->i32{
        if bp[i][j]!=-1{
            return bp[i][j]
        }
        let mut cost=1<<31-1;
        if i==j-1{
            bp[i][j]=i as i32;
            return i as i32
        }
        for ind in i+1..j{
            cost=cost.min(ind as i32+Solution::get_f(i,ind-1,bp).max(Solution::get_f(ind+1,j,bp)));
        }
        cost=cost.min(i as i32+Solution::get_f(i+1,j,bp));
        cost=cost.min(j as i32+Solution::get_f(i,j-1,bp));
        bp[i][j]=cost;
        cost

    }
}